//
// Created by ASUS on 2024/5/30/星期四.
//
#include <bits/stdc++.h>
using namespace std;

void preprocess(string s) {
	int n=s.length();
	vector<vector<int>> g(n, vector<int>(n, true)); //g[i][j]->s[i:j]是否是回文串
	for (int i = n - 1; i >= 0; --i) {
		for (int j = i + 1; j < n; ++j) {
			g[i][j] = (s[i] == s[j]) && g[i + 1][j - 1];
		}
	}
}

void preprocess1(string s) {
	int n=s.length();
	vector<vector<int>> g(n, vector<int>(n)); // g[i][j]->s[i:j]变成回文串需要修改的字符数
	for (int i = n - 1; i >= 0; --i) {
		for (int j = i + 1; j < n; ++j) {
			g[i][j] = (s[i] != s[j]) + g[i + 1][j - 1];
		}
	}
}
